/*
 * @lc app=leetcode.cn id=28 lang=typescript
 *
 * [28] 实现 strStr()
 */

// @lc code=start
function strStr(haystack: string, needle: string): number {
  const n = needle.length;
  const m = haystack.length;
  const index = new Array(26).fill(-1);
  const base = 'a'.charCodeAt(0);
  // 记录匹配串的字符下标
  for (let i = 0; i < n; i++) {
    const idx = needle.charCodeAt(i) - base;
    index[idx] = i;
  }
  let i = 0;
  while (i + n <= m) {
    let flag = 1;
    for (let j = 0; j < n; j++) {
      if (haystack[i + j] === needle[j]) continue;
      flag = 0;
      break;
    }
    if (flag === 1) return i;
    const idx = haystack[i + n] ? haystack[i + n].charCodeAt(0) - base : -1;
    i += n - index[idx];
  }

  return -1;
}
// @lc code=end
